/*
 * pi ф-я
 * vim:foldmethod=marker:
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


unsigned int *
prefix_func(const char *str, const int len, unsigned int *pi)
{
	unsigned int k = 0;
	unsigned int q;

	pi[0] = 0;
	for (q = 1; q < len; ++q) {
		while (k > 0 && str[k] != str[q])
			k = pi[k - 1];
		if (str[k] == str[q])
			k++;
		pi[q] = k;
	}

	return pi;
}

int
main(void)
{
	char *string;
	unsigned int *pi;
	unsigned int len = 0, i = 1;

	string = (char *) malloc(128002UL * sizeof *string);
	pi = (unsigned int *) calloc(128000UL, sizeof *pi);

	while (fgets(string, 128002, stdin)) {
		len = strlen(string);
		if (string[len - 1] == '\n') string[--len] = '\0';
		prefix_func(string, len, pi);

		i = 1;
		while (i < len)
			(void) printf("%d ", pi[i++]);
		putchar('\n');
	}

	free(pi);
	free(string);

	return 0;
}
